﻿#include <iostream>

/*
 * 链式存储的二叉树的四种遍历方式。分别分为递归和非递归两种。
 */
#define MaxTreeSize 10
typedef char TElemType;
TElemType Nil = '#';  // 用'#'表示空

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitBiTree(BiTree &BT) {
    BT = NULL;
}// InitBiTree


void CreateBiTree(BiTree &BT) {  // 按先序次序输入二叉树中结点的值，构造二叉树BT。变量Nil表示空(子)树。
    TElemType a;
    std::cin >> a;                                         // 输入结点的值
    if (a == Nil)                                        // 结点的值为空
        BT = NULL;
    else                                              // 结点的值不为空
    {
        BT = (BiTree) malloc(sizeof(BiTNode));             // 生成根结点
        if (!BT)
            exit(1);
        BT->data = a;                                     // 将值赋给T所指结点
        CreateBiTree(BT->lchild);                       // 递归构造左子树
        CreateBiTree(BT->rchild);                       // 递归构造右子树
    }
}// CreateBiTree

bool BiTreeEmpty(BiTree BT) {
    if (BT)
        return false;
    else
        return true;
}// BiTreeEmpty

void Visit(TElemType e) {           // 访问函数定义为输出操作
    std::cout << e << ' ';
}


int BiTreeDepth(BiTree BT) {
    int Lh, Rh;  // 最优子树的高度
    if (!BT)
        return 0;
    Lh = BiTreeDepth(BT->lchild);
    Rh = BiTreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}

void PreOrder(BiTree BT) {
    // 前序递归遍历
    if (BT) {
        printf("%d", BT->data);  // 打印根，相当于Visit(BT->data);
        PreOrder(BT->lchild);  // 进入左子树
        PreOrder(BT->rchild);  // 进入右子树
    }
}

void NRPreOrder(BiTree BT) {
    // 前序非递归遍历
    BiTNode *stack[MaxTreeSize];  // 递归工作栈
    int top = -1;  // 栈顶指针
    BiTNode *p;  // 树遍历指针
    if (BT != NULL) {
        stack[++top] = BT;      // 根结点入栈
        while (top > -1) {
            p = stack[top--];
            printf("%c", p->data);
            if (p->rchild != NULL)
                stack[++top] = p->rchild;
            if (p->lchild != NULL) {
                stack[++top] = p->lchild;
            }
        }
    }
}

void InOrder(BiTree BT) {
    // 中序递归遍历
    if (BT) {
        InOrder(BT->lchild);
        Visit(BT->data);
        InOrder(BT->rchild);
    }
}

void NRInOrder(BiTree BT) {
    BiTNode *stack[MaxTreeSize];
    int top = -1;
    BiTNode *p;
    while (top > -1 || p != NULL) {
        if (BT != NULL) {
            p = BT;
            while (p != NULL) {   // 将根结点至最左左结点全部压栈
                stack[++top] = p;
                p = p->lchild;
            }
            if (top > -1) {  // 当p没有左孩子结点
                p = stack[top--];  // p出栈并访问
                printf("%c", p->data);
                p = p->rchild;  // 转向访问右孩子结点
            }
        }
    }
}


void PostOrder(BiTree BT) {
    if (BT != NULL) {
        PostOrder(BT->lchild);
        PostOrder(BT->rchild);
        Visit(BT->data);
    }
}

void NRPostOrder(BiTree BT) {   // 后序非递归遍历二叉树BT(利用栈)
    BiTNode *stack[MaxTreeSize];
    int top = -1;            // 初始化栈S
    BiTree p, q;  // p是遍历指针， q是指向刚刚访问的结点
    int flag;   // 辅助变量
    if (BT != NULL) {
        p = BT;
        do {
            while (p != NULL) {  // 循环将所有左孩子入栈
                stack[++top] = p;
                p = p->lchild;
            }
            flag = 1;  // 辅助变量为1表示当前结点的左孩子为空或已经被访问过
            q = NULL;
            while (top > -1 && flag == 1) {
                p = stack[top];   //  取栈顶元素，并没有出栈
                if (p->rchild == q) {  // 其右孩子不存在或已访问
                    p = stack[top--];  // 栈顶元素出栈
                    printf("%c", p->data);
                    q = p;  // q指向刚刚访问的结点
                } else {
                    p = p->rchild;  // p指向其右孩子
                    flag = 0;
                }
            }
        } while (top > -1);
    }
}


void LevelOrder(BiTree BT) {
    // 层序遍历（从上到下，从左到右）
    BiTNode *p;  // 遍历指针
    BiTNode *Sequeue[MaxTreeSize];
    int front = 0, rear = 0;  // 对头指针
    if (BT) {  // 树非空
        // 根结点入队
        Sequeue[rear] = BT;
        rear = (rear + 1) % MaxTreeSize;
        while (front != rear) {  // 队列不空
            p = Sequeue[front];
            front = (front - 1) % MaxTreeSize;  // 对头元素出队，并赋值给p
            Visit(p->data);  // 访问p结点的值
            if (p->lchild != NULL) {
                Sequeue[rear] = p->lchild;
                rear = (rear + 1) % MaxTreeSize;  // p有左孩子，左孩子入队
            }
            if (p->rchild != NULL) {
                Sequeue[rear] = p->rchild;
                rear = (rear + 1) % MaxTreeSize;  // p有右孩子，右孩子入队
            }
        }
    }
}


void LevelPost_Invert(BiTree BT) {
    // 自下而上，从右到左的层次遍历
    // 这里的层次遍历序列与从上到下、从左到右的层次遍历序列相反，可以先按正常的层次遍历方式遍历后，出队的元素压栈，直到队列空，再栈中元素依次出栈访问。
    BiTNode *p;
    BiTNode *Sequeue[MaxTreeSize];
    BiTNode *stack[MaxTreeSize];
    int front = 0, rear = 0, top = -1;
    if (BT) {
        Sequeue[rear] = BT;
        rear = (rear + 1) % MaxTreeSize;  //  根结点入队
        while (front != rear) {   // 队列不空，对头元素出队并压栈
            p = Sequeue[front];
            front = (front + 1) % MaxTreeSize;
            stack[++top] = p;
        }
        if (p->lchild != NULL) {
            Sequeue[rear] = p->lchild;
            rear = (rear + 1) % MaxTreeSize;
        }
        if (p->rchild != NULL) {
            Sequeue[rear] = p->rchild;
            rear = (rear + 1) % MaxTreeSize;
        }
        // 队列为空，栈中元素依次出栈，并访问该出栈元素
        while(top>-1){
            p=stack[top--];
            Visit(p->data);
        }
    }
}

int main() {
    int i;
    BiTree BT, p, c;
    TElemType e1, e2;
    InitBiTree(BT);                                  // 初始化二叉树BT
    std::cout << "构造空二叉树后，树空否？" << BiTreeEmpty(BT);
    std::cout << "(1：是 0：否)。树的深度=" << BiTreeDepth(BT) << std::endl;
    std::cout << "请按先序输入二叉树(用'#'表示子树为空)：" << std::endl;
    CreateBiTree(BT);                                 // 建立二叉树BT
    std::cout << "建立二叉树后，树空否？" << BiTreeEmpty(BT);
    std::cout << "(1：是 0：否)。树的深度=" << BiTreeDepth(BT) << std::endl;
    std::cout << "先序递归遍历二叉树：";
    PreOrder(BT);                          // 先序递归遍历二叉树BT
    std::cout << std::endl << "中序递归遍历二叉树：";
    InOrder(BT);                           // 中序递归遍历二叉树BT
    std::cout << std::endl << "后序递归遍历二叉树：";
    PostOrder(BT);                          // 后序递归遍历二叉树BT
    std::cout << std::endl << "先序非递归遍历二叉树：";
    NRPreOrder(BT);                         // 先序非递归遍历二叉树BT
    std::cout << std::endl << "中序非递归遍历二叉树：";
    NRInOrder(BT);                          // 中序非递归遍历二叉树BT
    std::cout << std::endl << "后序非递归遍历二叉树：";
    NRPostOrder(BT);
    return 0;
}